/*
  Name: 哈夫曼算法 
  Copyright: 
  Author: 
  Date: 28-03-04 14:28
  Description: 
*/

#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED

#include <stdlib.h>
#include <string.h>

//哈夫曼树和哈夫曼编码的存储结构
typedef struct {
    int weight;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree;       //动态分配数组存储哈夫曼树 
typedef char * * HuffmanCode; //动态分配数组存储哈夫曼编码表 


//求哈夫曼编码的算法
//    w 存放n个字符的权值，构造哈夫曼树HT，并求出哈夫曼编码HC 
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
    // TODO (#1#): 编写哈夫曼编码的算法
/*  
    void Select(HuffmanTree,int,int&,int&);
    int i,m,s1,s2,c,f,start;
    HuffmanTree p;
    char *cd;
    
    if(n<=1) return ;//结点太少
    
    //初始化 
    m = 2*n-1;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
    for(p=HT+1,i=1; i<=n; ++i,++p,++w) //生成n个叶子结点 NOTE:课本有误
        p->weight = *w, p->parent = p->lchild = p->rchild  = 0;
    for( ; i<=m; ++i,++p)
        p->weight = p->parent = p->lchild = p->rchild  = 0;

    //构造哈夫曼树
    for(i=n+1; i<=m; ++i) {
        //在HT[1..i-1]中选择两个parent为0且weight最小的，序号为s1,s2
        Select(HT,i-1,s1,s2);
        //用s1和s2作为左右子树和并成一棵树i 
        HT[s1].parent = HT[s2].parent = i;
        HT[i].lchild = s1; HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight+HT[s2].weight;
    }
    
    //求哈夫曼编码
    HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
    cd = (char *)malloc(n*sizeof(char)); //临时工作空间
    for(i=1; i<=n; ++i) {
        start = n-1;
        cd[start] = '\0';
        for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
            if(HT[f].lchild==c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
        HC[i] = (char *)malloc((n-start+1)*sizeof(char));
        strcpy(HC[i], &cd[start]);
    }
    free(cd);
*/
}

void Select(HuffmanTree HT,int i,int& s1,int& s2)
{
    // TODO (#1#): 在HT[1..i]中选择两个parent为0且weight最小的，序号为s1,s2
/*
    int j;
    int w1,w2,s;
    //选出最小 s1
    for(j=1; j<=i; j++)
        if(HT[j].parent==0) break;
    s1 = j;
    w1 = HT[j].weight;
    for(j++; j<=i; j++)
        if(HT[j].parent==0&&HT[j].weight<w1)
            s1 = j, w1 = HT[j].weight;
    //选出次小 s2
    for(j=1; j<=i; j++)
        if(HT[j].parent==0&&j!=s1) break;
    s2 = j;
    w2 = HT[j].weight;
    for(j++; j<=i; j++)
        if(HT[j].parent==0&&j!=s1&&HT[j].weight<w2)
            s2 = j, w2 = HT[j].weight;
    //保持s1<s2
    if(s1>s2)
        s=s1, s1=s2, s2=s;
*/
}

#endif

